home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Almathera Ten Pack 2: CDPD 1
/
Almathera Ten on Ten - Disc 2: CDPD 1.iso
/
pd
/
101-125
/
105
/
bison
/
output.c
< prev
next >
Wrap
C/C++ Source or Header
|
1995-03-13
|
22KB
|
1,213 lines
/* Output the generated parsing program for bison,
copyright (C) 1984 Bob Corbett and Richard Stallman
Permission is granted to anyone to make or distribute verbatim copies of this program
provided that the copyright notice and this permission notice are preserved;
and provided that the recipient is not asked to waive or limit his right to
redistribute copies as permitted by this permission notice;
and provided that anyone possessing an executable copy
is granted access to copy the source code, in machine-readable form,
in some reasonable manner.
Permission is granted to distribute derived works or enhanced versions of
this program under the above conditions with the additional condition
that the entire derivative or enhanced work
must be covered by a permission notice identical to this one.
Anything distributed as part of a package containing portions derived
from this program, which cannot in current practice perform its function usefully
in the absense of what was derived directly from this program,
is to be considered as forming, together with the latter,
a single work derived from this program,
which must be entirely covered by a permission notice identical to this one
in order for distribution of the package to be permitted.
In other words, you are welcome to use, share and improve this program.
You are forbidden to forbid anyone else to use, share and improve
what you give them. Help stamp out software-hoarding! */
/* functions to output parsing data to various files. Entries are:
output_headers ()
Output constant strings to the beginning of certain files.
output_trailers()
Output constant strings to the ends of certain files.
output ()
Output the parsing tables and the parser code to ftable.
The parser tables consist of: (starred ones needed only for the semantic parser)
yytranslate = vector mapping yylex's token numbers into bison's token numbers.
* yyrhs = vector of items of all rules.
This is exactly what ritems contains.
* yyprhs[r] = index in yyrhs of first item for rule r.
yyr1[r] = symbol number of symbol that rule r derives.
yyr2[r] = number of symbols composing right hand side of rule r.
* yystos[s] = the symbol number of the symbol that leads to state s.
yydefact[s] = default rule to reduce with in state s,
when yytable doesn't specify something else to do.
Zero means the default is an error.
yydefgoto[i] = default state to go to after a reduction of a rule that
generates variable ntokens + i, except when yytable
specifies something else to do.
yypact[s] = index in yytable of the portion describing state s.
The lookahed token's type is used to index that portion
to find out what to do.
If the value in yytable is positive,
we shift the token and go to that state.
If the value is negative, it is minus a rule number to reduce by.
If the value is zero, the default action from yydefact[s] is used.
yypgoto[i] = the index in yytable of the portion describing
what to do after reducing a rule that derives variable i + ntokens.
This portion is indexed by the parser state number
as of before the text for this nonterminal was read.
The value from yytable is the state to go to.
yytable = a vector filled with portions for different uses,
found via yypact and yypgoto.
yycheck = a vector indexed in parallel with yytable.
It indicates, in a roundabout way, the bounds of the
portion you are trying to examine.
Suppose that the portion of yytable starts at index p
and the index to be examined within the portion is i.
Then if yycheck[p+i] != i, i is outside the bounds
of what is actually allocated, and the default
(from yydefact or yydefgoto) should be used.
Otherwise, yytable[p+i] should be used.
YYFINAL = the state number of the termination state.
YYFLAG = most negative short int. Used to flag ??
YYNTBASE = ntokens.
*/
#include <stdio.h>
#include "machine.h"
#include "new.h"
#include "files.h"
#include "gram.h"
#include "state.h"
#define MAXTABLE 32767
extern int tokensetsize;
extern int final_state;
extern core **state_table;
extern shifts **shift_table;
extern reductions **reduction_table;
extern short *accessing_symbol;
extern unsigned *LA;
extern short *LAruleno;
extern short *lookaheads;
extern char *consistent;
extern short *goto_map;
extern short *from_state;
extern short *to_state;
static int nvectors;
static int nentries;
static short **froms;
static short **tos;
static short *tally;
static short *width;
static short *actrow;
static short *state_count;
static short *order;
static short *base;
static short *pos;
static short *table;
static short *check;
static int lowzero;
static int high;
static char *guardstr[] = {
"extern int yyerror;\n",
"extern int yycost;\n",
"extern char * yymsg;\n",
"extern YYSTYPE yyval;\n\n",
"yyguard(n, yyvsp, yylsp)\n",
"register int n;\n",
"register YYSTYPE *yyvsp;\n",
"register YYLTYPE *yylsp;\n",
"{\n",
"yyerror = 0;\n",
"yycost = 0;\n",
"yymsg = 0;\n",
"switch (n)\n",
"{",
NULL
};
static char *actstr[] = {
"extern YYSTYPE yyval;\n",
"extern int yychar;\n",
"yyaction(n, yyvsp, yylsp)\n",
"register int n;\n",
"register YYSTYPE *yyvsp;\n",
"register YYLTYPE *yylsp;\n",
"{\n",
"switch (n)\n",
"{",
NULL
};
#define ACTSTR_SIMPLE "\n switch (yyn) {\n"
output_headers()
{
if (semantic_parser) {
fprintf(fguard, "\n#include \"%s\"\n", attrsfile);
emit(guardstr);
fprintf(faction, "\n#include \"%s\"\n", attrsfile);
emit(actstr);
} else {
fprintf(faction, ACTSTR_SIMPLE);
}
if (semantic_parser)
fprintf(ftable, "#include \"%s\"\n", attrsfile);
fprintf(ftable, "#include <stdio.h>\n\n");
}
output_trailers()
{
if (semantic_parser)
{
fprintf(fguard, "\n }\n}\n");
fprintf(faction, "\n }\n}\n");
}
else
fprintf(faction, "\n}\n");
}
output()
{
free_itemsets();
output_defines();
output_token_translations();
if (semantic_parser)
output_gram();
FREE(ritem);
if (semantic_parser)
output_stos();
output_rule_data();
output_actions();
output_parser();
output_program();
}
output_token_translations()
{
register int i, j;
if (translations)
{
fprintf(ftable, "\n#define YYTRANSLATE(x) (yytranslate[x])\n");
if (ntokens < 127) /* play it very safe; check maximum element value. */
fprintf(ftable, "\nstatic char yytranslate[] = { 0");
else
fprintf(ftable, "\nstatic short yytranslate[] = { 0");
j = 10;
for (i = 1; i <= max_user_token_number; i++)
{
putc(',', ftable);
if (j >= 10)
{
putc('\n', ftable);
j = 1;
}
else
{
j++;
}
fprintf(ftable, "%6d", token_translations[i]);
}
fprintf(ftable, "\n};\n");
}
else
{
fprintf(ftable, "\n#define YYTRANSLATE(x) (x)\n");
}
}
output_gram()
{
register int i;
register int j;
register short *sp;
fprintf(ftable, "\nstatic short yyprhs[] = { 0");
j = 10;
for (i = 1; i < nrules; i++)
{
putc(',', ftable);
if (j >= 10)
{
putc('\n', ftable);
j = 1;
}
else
{
j++;
}
fprintf(ftable, "%6d", rrhs[i]);
}
fprintf(ftable, "\n};\n\nstatic short yyrhs[] = {%6d", ritem[0]);
j = 10;
for (sp = ritem + 1; *sp; sp++)
{
putc(',', ftable);
if (j >= 10)
{
putc('\n', ftable);
j = 1;
}
else
{
j++;
}
if (*sp > 0)
fprintf(ftable, "%6d", *sp);
else
fprintf(ftable, " 0");
}
fprintf(ftable, "\n};\n");
}
output_stos()
{
register int i;
register int j;
fprintf(ftable, "\nstatic short yystos[] = { 0");
j = 10;
for (i = 1; i < nstates; i++)
{
putc(',', ftable);
if (j >= 10)
{
putc('\n', ftable);
j = 1;
}
else
{
j++;
}
fprintf(ftable, "%6d", accessing_symbol[i]);
}
fprintf(ftable, "\n};\n");
}
output_rule_data()
{
register int i;
register int j;
fprintf(ftable, "\nstatic short yyr1[] = { 0");
j = 10;
for (i = 1; i <= nrules; i++)
{
putc(',', ftable);
if (j >= 10)
{
putc('\n', ftable);
j = 1;
}
else
{
j++;
}
fprintf(ftable, "%6d", rlhs[i]);
}
FREE(rlhs + 1);
fprintf(ftable, "\n};\n\nstatic short yyr2[] = { 0");
j = 10;
for (i = 1; i < nrules; i++)
{
putc(',', ftable);
if (j >= 10)
{
putc('\n', ftable);
j = 1;
}
else
{
j++;
}
fprintf(ftable, "%6d", rrhs[i + 1] - rrhs[i] - 1);
}
putc(',', ftable);
if (j >= 10)
putc('\n', ftable);
fprintf(ftable, "%6d\n};\n", nitems - rrhs[nrules] - 1);
FREE(rrhs + 1);
}
output_defines()
{
fprintf(ftable, "\n\n#define\tYYFINAL\t\t%d\n", final_state);
fprintf(ftable, "#define\tYYFLAG\t\t%d\n", MINSHORT);
fprintf(ftable, "#define\tYYNTBASE\t%d\n", ntokens);
}
/* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable and yycheck. */
output_actions()
{
nvectors = nstates + nvars;
froms = NEW2(nvectors, short *);
tos = NEW2(nvectors, short *);
tally = NEW2(nvectors, short);
width = NEW2(nvectors, short);
token_actions();
free_shifts();
free_reductions();
FREE(lookaheads);
FREE(LA);
FREE(LAruleno);
FREE(accessing_symbol);
goto_actions();
FREE(goto_map);
FREE(from_state);
FREE(to_state);
sort_actions();
pack_table();
output_base();
output_table();
output_check();
}
/* figure out the actions for the specified state, indexed by lookahead token type.
The yydefact table is output now. The detailed info
is saved for putting into yytable later. */
token_actions()
{
register int i;
register int j;
register int k;
actrow = NEW2(ntokens, short);
k = action_row(0);
fprintf(ftable, "\nstatic short yydefact[] = {%6d", k);
save_row(0);
j = 10;
for (i = 1; i < nstates; i++)
{
putc(',', ftable);
if (j >= 10)
{
putc('\n', ftable);
j = 1;
}
else
{
j++;
}
k = action_row(i);
fprintf(ftable, "%6d", k);
save_row(i);
}
fprintf(ftable, "\n};\n");
FREE(actrow);
}
/* Decide what to do for each type of token if seen as the lookahead token in specified state.
The value returned is used as the default action (yydefact) for the state.
In addition, actrow is filled with what to do for each kind of token,
index by symbol number, with zero meaning do the default action.
This is where conflicts are resolved. The loop over lookahead rules
considered lower-numbered rules last, and the last rule considered that likes
a token gets to handle it. */
int
action_row(state)
int state;
{
register int i;
register int j;
register int k;
register int m;
register int n;
register int count;
int default_rule;
int nreds;
int maxcount;
int rule;
int shift_state;
int symbol;
unsigned mask;
register unsigned *wordp;
register reductions *redp;
register shifts *shiftp;
int nodefault = 0; /* set nonzero to inhibit having any default reduction */
for (i = 0; i < ntokens; i++)
actrow[i] = 0;
default_rule = 0;
nreds = 0;
redp = reduction_table[state];
if (redp)
{
nreds = redp->nreds;
if (nreds >= 1)
{
/* loop over all the rules available here which require lookahead */
m = lookaheads[state];
n = lookaheads[state + 1];
for (i = n - 1; i >= m; i--)
{
rule = - LAruleno[i];
wordp = LA + i * tokensetsize;
mask = 1;
/* and find each token which the rule finds acceptable to come next */
for (j = 0; j < ntokens; j++)
{
/* and record this rule as the rule to use if that token follows. */
if (mask & *wordp)
actrow[j] = rule;
mask <<= 1;
if (mask == 0)
{
mask = 1;
wordp++;
}
}
}
}
}
shiftp = shift_table[state];
/* now see which tokens are allowed for shifts in this state.
For them, record the shift as the thing to do. So shift is preferred to reduce. */
if (shiftp)
{
k = shiftp->nshifts;
for (i = 0; i < k; i++)
{
shift_state = shiftp->shifts[i];
if (! shift_state) continue;
symbol = accessing_symbol[shift_state];
if (ISVAR(symbol))
break;
actrow[symbol] = shift_state;
/* do not use any default reduction if there is a shift for error */
if (symbol == error_token_number) nodefault = 1;
}
}
/* now find the most common reduction and make it the default action for this state. */
if (nreds >= 1 && ! nodefault)
{
if (consistent[state])
default_rule = redp->rules[0];
else
{
maxcount = 0;
for (i = m; i < n; i++)
{
count = 0;
rule = - LAruleno[i];
for (j = 0; j < ntokens; j++)
{
if (actrow[j] == rule)
count++;
}
if (count > maxcount)
{
maxcount = count;
default_rule = rule;
}
}
/* actions which match the default are replaced with zero,
which means "use the default" */
if (maxcount > 0)
{
for (j = 0; j < ntokens; j++)
{
if (actrow[j] == default_rule)
actrow[j] = 0;
}
default_rule = - default_rule;
}
}
}
return (default_rule);
}
save_row(state)
int state;
{
register int i;
register int count;
register short *sp;
register short *sp1;
register short *sp2;
count = 0;
for (i = 0; i < ntokens; i++)
{
if (actrow[i] != 0)
count++;
}
if (count == 0)
return;
froms[state] = sp1 = sp = NEW2(count, short);
tos[state] = sp2 = NEW2(count, short);
for (i = 0; i < ntokens; i++)
{
if (actrow[i] != 0)
{
*sp1++ = i;
*sp2++ = actrow[i];
}
}
tally[state] = count;
width[state] = sp1[-1] - sp[0] + 1;
}
/* figure out what to do after reducing with each rule,
depending on the saved state from before the beginning
of parsing the data that matched this rule.
The yydefgoto table is output now. The detailed info
is saved for putting into yytable later. */
goto_actions()
{
register int i;
register int j;
register int k;
state_count = NEW2(nstates, short);
k = default_goto(ntokens);
fprintf(ftable, "\nstatic short yydefgoto[] = {%6d", k);
save_column(ntokens, k);
j = 10;
for (i = ntokens + 1; i < nsyms; i++)
{
putc(',', ftable);
if (j >= 10)
{
putc('\n', ftable);
j = 1;
}
else
{
j++;
}
k = default_goto(i);
fprintf(ftable, "%6d", k);
save_column(i, k);
}
fprintf(ftable, "\n};\n");
FREE(state_count);
}
int
default_goto(symbol)
int symbol;
{
register int i;
register int m;
register int n;
register int default_state;
register int maxcount;
m = goto_map[symbol];
n = goto_map[symbol + 1];
if (m == n)
return (-1);
for (i = 0; i < nstates; i++)
state_count[i] = 0;
for (i = m; i < n; i++)
state_count[to_state[i]]++;
maxcount = 0;
default_state = -1;
for (i = 0; i < nstates; i++)
{
if (state_count[i] > maxcount)
{
maxcount = state_count[i];
default_state = i;
}
}
return (default_state);
}
save_column(symbol, default_state)
int symbol;
int default_state;
{
register int i;
register int m;
register int n;
register short *sp;
register short *sp1;
register short *sp2;
register int count;
register int symno;
m = goto_map[symbol];
n = goto_map[symbol + 1];
count = 0;
for (i = m; i < n; i++)
{
if (to_state[i] != default_state)
count++;
}
if (count == 0)
return;
symno = symbol - ntokens + nstates;
froms[symno] = sp1 = sp = NEW2(count, short);
tos[symno] = sp2 = NEW2(count, short);
for (i = m; i < n; i++)
{
if (to_state[i] != default_state)
{
*sp1++ = from_state[i];
*sp2++ = to_state[i];
}
}
tally[symno] = count;
width[symno] = sp1[-1] - sp[0] + 1;
}
/* the next few functions decide how to pack
the actions and gotos information into yytable. */
sort_actions()
{
register int i;
register int j;
register int k;
register int t;
register int w;
order = NEW2(nvectors, short);
nentries = 0;
for (i = 0; i < nvectors; i++)
{
if (tally[i] > 0)
{
t = tally[i];
w = width[i];
j = nentries - 1;
while (j >= 0 && (width[order[j]] < w))
j--;
while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
j--;
for (k = nentries - 1; k > j; k--)
order[k + 1] = order[k];
order[j + 1] = i;
nentries++;
}
}
}
pack_table()
{
register int i;
register int place;
register int state;
base = NEW2(nvectors, short);
pos = NEW2(nentries, short);
table = NEW2(MAXTABLE, short);
check = NEW2(MAXTABLE, short);
lowzero = 0;
high = 0;
for (i = 0; i < nvectors; i++)
base[i] = MINSHORT;
for (i = 0; i < MAXTABLE; i++)
check[i] = -1;
for (i = 0; i < nentries; i++)
{
state = matching_state(i);
if (state < 0)
place = pack_vector(i);
else
place = base[state];
pos[i] = place;
base[order[i]] = place;
}
for (i = 0; i < nvectors; i++)
{
FREE(froms[i]);
FREE(tos[i]);
}
FREE(froms);
FREE(tos);
FREE(pos);
}
int
matching_state(vector)
int vector;
{
register int i;
register int j;
register int k;
register int t;
register int w;
register int match;
int prev;
i = order[vector];
if (i >= nstates)
return (-1);
t = tally[i];
w = width[i];
for (prev = vector - 1; prev >= 0; prev--)
{
j = order[prev];
if (width[j] != w || tally[j] != t)
return (-1);
match = 1;
for (k = 0; match && k < t; k++)
{
if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
match = 0;
}
if (match)
return (j);
}
return (-1);
}
int
pack_vector(vector)
int vector;
{
register int i;
register int j;
register int k;
register int t;
register int loc;
register int ok;
register short *from;
register short *to;
i = order[vector];
t = tally[i];
if (t == 0)
berror("pack_vector");
from = froms[i];
to = tos[i];
for (j = lowzero - from[0]; j < MAXTABLE; j++)
{
ok = 1;
for (k = 0; ok && k < t; k++)
{
loc = j + from[k];
if (loc > MAXTABLE)
fatal("maximum table size exceeded");
if (table[loc] != 0)
ok = 0;
}
for (k = 0; ok && k < vector; k++)
{
if (pos[k] == j)
ok = 0;
}
if (ok)
{
for (k = 0; k < t; k++)
{
loc = j + from[k];
table[loc] = to[k];
check[loc] = from[k];
}
while (table[lowzero] != 0)
lowzero++;
if (loc > high)
high = loc;
return (j);
}
}
berror("pack_vector");
}
/* the following functions output yytable, yycheck
and the vectors whose elements index the portion starts */
output_base()
{
register int i;
register int j;
fprintf(ftable, "\nstatic short yypact[] = {%6d", base[0]);
j = 10;
for (i = 1; i < nstates; i++)
{
putc(',', ftable);
if (j >= 10)
{
putc('\n', ftable);
j = 1;
}
else
{
j++;
}
fprintf(ftable, "%6d", base[i]);
}
fprintf(ftable, "\n};\n\nstatic short yypgoto[] = {%6d", base[nstates]);
j = 10;
for (i = nstates + 1; i < nvectors; i++)
{
putc(',', ftable);
if (j >= 10)
{
putc('\n', ftable);
j = 1;
}
else
{
j++;
}
fprintf(ftable, "%6d", base[i]);
}
fprintf(ftable, "\n};\n");
FREE(base);
}
output_table()
{
register int i;
register int j;
fprintf(ftable, "\n\n#define\tYYLAST\t\t%d\n\n", high);
fprintf(ftable, "\nstatic short yytable[] = {%6d", table[0]);
j = 10;
for (i = 1; i <= high; i++)
{
putc(',', ftable);
if (j >= 10)
{
putc('\n', ftable);
j = 1;
}
else
{
j++;
}
fprintf(ftable, "%6d", table[i]);
}
fprintf(ftable, "\n};\n");
FREE(table);
}
output_check()
{
register int i;
register int j;
fprintf(ftable, "\nstatic short yycheck[] = {%6d", check[0]);
j = 10;
for (i = 1; i <= high; i++)
{
putc(',', ftable);
if (j >= 10)
{
putc('\n', ftable);
j = 1;
}
else
{
j++;
}
fprintf(ftable, "%6d", check[i]);
}
fprintf(ftable, "\n};\n");
FREE(check);
}
/* copy the parser code into the ftable file at the end. */
output_parser()
{
register int c;
FILE *fpars;
if (pure_parser)
fprintf(ftable, "#define YYIMPURE 1\n\n");
else
fprintf(ftable, "#define YYPURE 1\n\n");
if (semantic_parser)
fpars = fparser;
else fpars = fparser1;
c = getc(fpars);
while (c != EOF)
{
if (c == '$')
fprintf(ftable, "#include \"%s\"\n", actfile);
else
putc(c, ftable);
c = getc(fpars);
}
}
output_program()
{
register int c;
extern int lineno;
fprintf(ftable, "#line %d \"%s\"\n", lineno, infile);
c = getc(finput);
while (c != EOF)
{
putc(c, ftable);
c = getc(finput);
}
}
free_itemsets()
{
register core *cp, *cptrail;
FREE(state_table);
for (cp = first_state; cp;) {
cptrail = cp;
cp = cp->next;
FREE(cptrail);
}
}
free_shifts()
{
register shifts *sp, *sptrail;
FREE(shift_table);
for (sp = first_shift; sp;) {
sptrail = sp;
sp = sp->next;
FREE(sptrail);
}
}
free_reductions()
{
register reductions *rp, *rptrail;
FREE(reduction_table);
for (rp = first_reduction; rp;) {
rptrail = rp;
rp = rp->next;
FREE(rptrail);
}
}
emit (stp)
char **stp;
{
while (stp && *stp) {
fprintf (faction, "%s", *stp++);
}
}